/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
// hack version
 var isPalindrome = function(head) {
    const stack = []
    let cur =  head
    while(cur){
        stack.push(cur.val)
        cur = cur.next
    }
    while(head && head.val === stack.pop()){
        head = head.next
    }
    return !stack.length
};

// good version
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
 var isPalindrome = function(head) {
    let p = new ListNode(null)
    p.next = head
    let slow = p;
    let quick = p
    while(quick && quick.next){
        slow = slow.next
        quick = quick.next.next
    }
    let cur = slow.next
    let pre = null
    while(cur){
        let temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }
    slow.next = null
    while(pre){
        if(pre.val !== head.val){
            return false
        }
        pre = pre.next
        head = head.next
    }
    return true
};